package com.fanshuai2.niuke.search.dfs;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * 输入两个整数，分别表示二维数组的行数，列数。再输入相应的数组，其中的1表示墙壁，0表示可以走的路。数据保证有唯一解,不考虑有多解的情况，即迷宫只有一条通道。
 *
 * 输入：
 * 5 5
 * 0 1 0 0 0
 * 0 1 1 1 0
 * 0 0 0 0 0
 * 0 1 1 1 0
 * 0 0 0 1 0
 *
 * 输出：
 * (0,0)
 * (1,0)
 * (2,0)
 * (2,1)
 * (2,2)
 * (2,3)
 * (2,4)
 * (3,4)
 * (4,4)
 *
 *
 * 输入：
 * 5 5
 * 0 1 0 0 0
 * 0 1 0 1 0
 * 0 0 0 0 1
 * 0 1 1 1 0
 * 0 0 0 0 0
 *
 * 输出：
 * (0,0)
 * (1,0)
 * (2,0)
 * (3,0)
 * (4,0)
 * (4,1)
 * (4,2)
 * (4,3)
 * (4,4)
 */
public class Migong {
    static class Position {
        int x;
        int y;
        public Position(int x, int y) {
            this.x = x;
            this.y = y;
        }
        public String toString() {
            return "(" + x + "," + y + ")";
        }
    }
    static class ListValue {
        List<Position> path = new ArrayList<>();
        public void setPath(List<Position> positions) {
            this.path = positions;
        }
        public int getSize() {
            if (path.size() == 0) {
                return Integer.MAX_VALUE;
            } else {
                return path.size();
            }
        }
    }

    static List<Position> getPath(int[][] migong) {
        boolean[][] visited = new boolean[migong.length][migong[0].length];

        ListValue fullPath = new ListValue();
        List<Position> path = new ArrayList<Position>();
        path.add(new Position(0, 0));
        getPath0(migong, visited, 0, 0, path, fullPath);
        return fullPath.path;
    }

    static void getPath0(int[][] migong, boolean[][] visited,
                         int i, int j, List<Position> path, ListValue fullPath) {
        int mlen = migong.length;
        int nlen = migong[0].length;
        if (i == mlen - 1 && j == nlen - 1) {
            if (path.size() < fullPath.getSize()) {
                fullPath.setPath(new ArrayList<>(path));
            }
            return;
        }
        if (visited[i][j]) {
            return;
        }
        visited[i][j] = true;

        if (i + 1 < mlen && migong[i + 1][j] == 0) {
            path.add(new Position(i + 1, j));
            getPath0(migong, visited, i + 1, j, path, fullPath);
            path.remove(path.size() - 1);
        }
        if (j + 1 < nlen && migong[i][j + 1] == 0) {
            path.add(new Position(i, j + 1));
            getPath0(migong, visited, i, j + 1, path, fullPath);
            path.remove(path.size() - 1);
        }
        if (i - 1 >= 0 && migong[i - 1][j] == 0) {
            path.add(new Position(i - 1, j));
            getPath0(migong, visited, i - 1, j, path, fullPath);
            path.remove(path.size() - 1);
        }
        if (j - 1 >= 0 && migong[i][j - 1] == 0) {
            path.add(new Position(i, j - 1));
            getPath0(migong, visited, i, j - 1, path, fullPath);
            path.remove(path.size() - 1);
        }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        while (in.hasNextInt()) {
            int m = in.nextInt();
            int n = in.nextInt();
            int[][] migong = new int[m][n];
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    migong[i][j] = in.nextInt();
                }
            }
            List<Position> fullpath = getPath(migong);
            for (Position pos : fullpath) {
                System.out.println(pos.toString());
            }
        }
    }
}
